package com.pan.alg.leecode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Symmetrical {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

    }

    boolean isSymmetrical(TreeNode pRoot) {

        return isSame(pRoot,pRoot);
    }

    private boolean isSame(TreeNode left, TreeNode right) {
        if(left==null&&right==null){
            return true;
        }else if((left==null&&right!=null)||(left!=null&&right==null)){
            return false;
        }else if(left.val!=right.val){
            return false;
        }
        return isSame(left.left,right.right)&&isSame(left.right,right.left);
    }

    /**
     * 采用层序遍历进行对比
     * @param pRoot
     * @return
     */
    boolean isSymmetrical2(TreeNode pRoot) {
        if(pRoot==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.add(pRoot.left);
        queue.add(pRoot.right);
        while (queue.size()!=0){
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();
            if(leftNode==null&&rightNode==null){
                continue;
            }
            boolean isNotEqualNode = (leftNode==null&&rightNode!=null)||(leftNode!=null&&rightNode==null)||leftNode.val!=rightNode.val;
            if(isNotEqualNode){
                return false;
            }

            queue.add(leftNode.left);
            queue.add(rightNode.right);
            queue.add(leftNode.right);
            queue.add(rightNode.left);
        }
        return true;
    }

}
